package algorithm.BST2DoubleLinkedList;

/*
给定一个搜索二叉树的头结点head，请转换成一个有序的双向链表，返回其头结点
先序遍历 -> 中序遍历？
 */
public class BST2DoubleLinkedList {
    public static class Node {
        public Node left;
        public Node right;
        public int val;

        public Node(Node left, Node right, int val) {
            this.left = left;
            this.right = right;
            this.val = val;
        }
    }
    public static class Info {
        Node start;
        Node end;

        public Info(Node start, Node end) {
            this.start = start;
            this.end = end;
        }

        @Override
        public String toString() {
            String str = "head:";
            Node start = this.start;
            Node cur = start;
            while (cur != null) {
                str = str.concat(cur.val + ", ");
                cur = cur.right;
            }
            str = str.concat("\n" + "tail:");
            cur = this.end;
            while (cur != null) {
                str = str.concat(cur.val + ", ");
                cur = cur.left;
            }
            return str;
        }
    }

    /*
    返回最左和最右节点
     */
    public static Info process(Node head) {
        if (head == null)
            return new Info(null, null);

        Info lChild = process(head.left);
        Info rChild = process(head.right);

        head.left = lChild.end;
        if (lChild.end != null) {
            lChild.end.right = head;
        }

        head.right = rChild.start;
        if (rChild.start != null) {
            rChild.start.left = head;
        }

        Node s = lChild.start == null ? head : lChild.start;
        Node e = rChild.end == null ? head : rChild.end;
        return new Info(s, e);
    }

    public static void main(String[] args) {
        Node node = new Node(
                new Node(
                        new Node(null, null, 2),
                        null,
                        3
                ),
                new Node(
                        new Node(null, null, 6),
                        new Node(null, null, 8),
                        7
                ),
                5
        );

        if (node == null)
            return;
        Info info = process(node);
        System.out.println(info);
    }
}
